﻿using System;
using System.Collections.Generic;

namespace Quick_Sort
{
    static class QuickSort<TComparable> where TComparable: IComparable<TComparable>
    {
        private static IList<TComparable> _collection;
        private static Random randomNumber = new Random();
        private static bool _ascending;

        public static TCollection Sort<TCollection>(TCollection collection, bool ascending = true)
            where TCollection : IList<TComparable>
        {
            _ascending = ascending;
            _collection = collection;

            QuickSortHelper(0, collection.Count - 1);

            return (TCollection)_collection;
        }

        public static TCollection Sort<TCollection>(TCollection collection, int left, int right, bool ascending = true)
            where TCollection : IList<TComparable>
        {
            _ascending = ascending;
            _collection = collection;

            QuickSortHelper(left, right);

            return (TCollection)_collection;
        }

        private static void QuickSortHelper(int left, int right)
        {
            if (left < right)
            {
                int pivot = FindPivot(left, right);
                QuickSortHelper(left, pivot - 1);
                QuickSortHelper(pivot + 1, right);
            }
        }

        private static int FindPivot(int left, int right)
        {
            int randomPivot = randomNumber.Next(left, right);

            Swap(right, randomPivot);
            return Partition(left, right);
        }

        private static int Partition(int left, int right)
        {            
            TComparable pivotValue = _collection[right];
            int newPivot = left;

            for (int i = left; i < right; i++)
            {
                if (_collection[i].CompareTo(pivotValue) == (_ascending ? 1 : -1))
                {
                    Swap(i, newPivot);
                    ++newPivot;
                }
            }

            _collection[right] = _collection[newPivot];
            _collection[newPivot] = pivotValue;

            return newPivot;
        }

        private static void Swap(int indexOne, int indexTwo)
        {
            TComparable temp = _collection[indexOne];
            _collection[indexOne] = _collection[indexTwo];
            _collection[indexTwo] = temp;
        }
    }
}
